package com.company.algo.SearchAlgorithm.BFS;

import java.util.*;

/**
 * 752. 打开转盘锁
 做的时候发现一个问题，
 如果是在q.offer的同时标识已访问，如
 if(!visited.contains(down)){
     q.offer(down);
     visited.add(down);
 }
 则不会超时
 -------------------------------------------------
 而如果是q.poll得到cur，再将cur标记为已访问，则会超时
 String cur = q.poll();
 visited.add(cur);
 if(!visited.contains(down)){
     q.offer(down);
 }
 -----------------------------------------------
 原因：在q.offer的同时标识已访问，会提前进行剪枝，避免后续大量不必要的运行逻辑进入线程中
 */
public class OpenLock {
    //将s[j]向上拨动一次
    public String plusOne(String s, int j){
        char[] ch = s.toCharArray();
        if(ch[j]=='9') ch[j] = '0';
        else ch[j] += 1;
        return new String(ch);
    }
    //将s[j]向下拨动一次
    public String minusOne(String s, int j){
        char[] ch = s.toCharArray();
        if(ch[j]=='0') ch[j] = '9';
        else ch[j] -= 1;
        return new String(ch);
    }
    //需要记录哪些密码被用过(visited)，死锁情况(deads)
    public int openLock(String[] deadends, String target) {
        HashSet<String> deads = new HashSet<>();
        for(String s : deadends) deads.add(s);
        HashSet<String> visited = new HashSet<>();
        Queue<String> q = new LinkedList<>();
        q.offer("0000");
        int step = 0;
        visited.add("0000");
        while(!q.isEmpty()){
            for(int i = q.size(); i > 0; i--){
                String cur = q.poll();
                if(deads.contains(cur)) continue;
                if(cur.equals(target)) return step;
                for(int j=0; j<4; j++){
                    String up = plusOne(cur, j);
                    if(!visited.contains(up)){
                        q.offer(up);
                        visited.add(up);
                    }
                    String down = minusOne(cur, j);
                    if(!visited.contains(down)){
                        q.offer(down);
                        visited.add(down);
                    }
                }
            }
            step++;
        }
        return -1;
    }
}
